package com.github.hgkmail.hello.leetcode101.binarysearch;

//旋转排序数组说明二分只需要一半的元素有单调性
public class LC33SearchInRotatedSortedArray {

    public int search(int[] nums, int target) {
        //base case
        if (nums.length==0) {
            return -1;
        }
        if (nums.length==1) {
            return nums[0]==target ? 0 : -1;
        }
        //二分，左闭右闭
        int l=0;
        int r=nums.length-1;
        int mid;
        while (l<=r) {
            mid=l+(r-l)/2;
            if (nums[mid]==target) {
                return mid;
            }
            if (nums[mid]>=nums[l]) { //左边有序
                if (target>=nums[l] && target<=nums[mid]) { //target在里面
                    r=mid-1;
                } else { //target不在里面，那肯定在另一边
                    l=mid+1;
                }
            } else { //右边有序
                if (target>=nums[mid] && target<=nums[r]) { //target在里面
                    l=mid+1;
                } else {
                    r=mid-1;
                }
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new LC33SearchInRotatedSortedArray().search(new int[]{4,5,6,7,0,1,2}, 0));
    }
}
